Ordering products over the internet for home delivery is an extremely popular way of shopping. Fulfilling such orders in a timely, accurate and efficient manner is logistically challenging to say the least. Clicking the “check out” button in a virtual shopping cart creates an “order.” The order includes a listing of items that are to be shipped to a particular address. The process of “fulfillment” involves physically taking or “picking” these items from a large warehouse, packing them, and shipping them to the designated address. An important goal of the order-fulfillment process is thus to ship as many items in as short a time as possible.
The order-fulfillment process typically takes place in a large warehouse that contains many products, including those listed in the order. Among the tasks of order fulfillment is therefore that of traversing the warehouse to find and collect the various items listed in an order. In addition, the products that will ultimately be shipped first need to be received in the warehouse and stored or “placed” in storage bins in an orderly fashion throughout the warehouse so they can be readily retrieved for shipping.
In a large warehouse, the goods that are being delivered and ordered can be stored in the warehouse very far apart from each other and dispersed among a great number of other goods. With an order-fulfillment process using only human operators to pick and place the goods requires the operators to do a great deal of walking and can be inefficient and time consuming. Since the efficiency of the fulfillment process is a function of the number of items shipped per unit time, increased time reduces pick place efficiency.
In order to increase efficiency, robots may be used to perform functions of humans or they may be used to supplement human activities. For example, robots may be assigned to “place” a number of items in various locations dispersed throughout the warehouse or to “pick” items from various locations for packing and shipping. The picking and placing may be done by the robot alone or with the assistance of human operators. For example, in the case of a pick operation, the human operator would pick items from shelves and place them on the robots or, in the case of a place operation, the human operator would pick items from the robot and place them on the shelves.
In a busy operation, many robots may need to navigate the warehouse space rapidly while avoiding fixed obstacles, such as shelves and walls, as well as dynamic obstacles, such as human operators and other robots. To do this, robots may utilize on board laser-radar and a mapping technique called simultaneous localization and mapping (SLAM), which is a computational problem of constructing and updating a map of an environment. As the robot begins to traverse the environment, e.g. a warehouse, it uses its laser radar to determine if there are any obstacles in its path, either fixed or dynamic, and iteratively updates its path to its destination to avoid observed objects. The robot may assess and potentially re-plan its route many times per second, e.g. about once every 50 milliseconds.
This is a complex and computationally challenging process for robots and can result in numerous path changes and inefficiencies in the paths selected by robots to get to their destinations.